package com.mashibing.class16;

import java.util.*;

public class Code03_TopologySort {
    // directed graph and no loop
    public static List<Node> sortedTopology(Graph graph) {
        // key 某个节点   value 剩余的入度
        HashMap<Node, Integer> inMap = new HashMap<Node, Integer>();
        // 只有剩余入度为0的点，才进入这个队列
        Queue<Node> zeroInQueue = new LinkedList<Node>();
        // 将初始化节点队列中, 入度为0的节点插入zeroInQueue中.
        for (Node node : graph.nodes.values()) {
            inMap.put(node, node.in);
            if (node.in == 0) {
                zeroInQueue.add(node);
            }
        }
        // result 用于存储所有排序后的结果
        List<Node> result = new ArrayList<Node>();
        while (!zeroInQueue.isEmpty()) {
            // 弹出一个入度为0的节点
            Node cur = zeroInQueue.poll();
            // 将这个入度为0的节点加入 result(存储排序后的变量) 集合中.
            result.add(cur);
            // 遍历当前入度为0的节点的所有邻居节点
            for (Node next : cur.nexts) {
                //将遍历当前的邻居节点的入度值 减 1  (其目的是 消除当前弹出节点 对其邻居节点的影响)
                inMap.put(next, inMap.get(next) - 1);
                // 如果遍历当前邻居节点的入度值 为0 的话, 直接加入 zeroInQueue 中
                if (inMap.get(next) == 0) {
                    zeroInQueue.add(next);
                }
            }
        }
        return result;
    }
}
